package alogrithm.tree;

import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 二叉树
 * @author christm
 *
 */
public class Btree<T> {
	
	public void visitBefore(Visitor<T> visitor,Node<T> node){
		if(node!=null){
			visitor.visit(node);
			visitBefore(visitor,node.getLeft());
			visitBefore(visitor, node.getRight());
		}
	}
	
	public void visitMiddle(Visitor<T> visitor,Node<T> node){
		if(node!=null){
			visitMiddle(visitor,node.getLeft());
			visitor.visit(node);
			visitMiddle(visitor,node.getRight());
		}
	}
	
	public void visitAfter(Visitor<T> visitor,Node<T> node){
		if(node!=null){
			visitAfter(visitor, node.getLeft());
			visitAfter(visitor, node.getRight());
			visitor.visit(node);
		}
	}
	
	public void visitLayer(NodeVisitor<T> visitor,Node<T> root){
		Queue<Node<T>> queue=new LinkedBlockingQueue<Node<T>>();
		queue.offer(root);
		do{
			Node<T> current=queue.poll();
			visitor.visit(current);
			
			if(current.getLeft()!=null){
				queue.offer(current.getLeft());
			}
			
			if(current.getRight()!=null){
				queue.offer(current.getRight());
			}
		}while(!queue.isEmpty());
	}
	
	public int maxHeight(Node<T> root){
		int left,right=0;
		if(root!=null){
			left=maxHeight(root.getLeft());
			right=maxHeight(root.getRight());
			return Math.max(left, right)+1;
		}else{
			return 0;
		}
	}
	
	/**
	 * 			A
	 *       B     C
	 *     D     E   F 
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		Btree<String> tree=new Btree<String>();
		Node<String> root=new Node<String>(null,"A");
		Node<String> b=new Node<String>(root,"B");
		Node<String> c=new Node<String>(root,"C");
		Node<String> d=new Node<String>(b,"D");
		
		Node<String> e=new Node<String>(c,"E");
		Node<String> f=new Node<String>(c,"F");
		
		root.setLeft(b);
		root.setRight(c);
		b.setLeft(d);
		c.setLeft(e);
		c.setRight(f);
		
		//先序遍历，预期的序列为A B D C E F
		NodeVisitor<String> visitor=new NodeVisitor<String>();
		tree.visitBefore(visitor, root);
		visitor.print();
		visitor.clear();
		
		//中序遍历,D B A E C F
		tree.visitMiddle(visitor, root);
		visitor.print();
		visitor.clear();
		
		//后序遍历,D B E F C A
		tree.visitAfter(visitor, root);
		visitor.print();
		visitor.clear();
		
		//层序遍历 A B C D E F
		tree.visitLayer(visitor, root);
		visitor.print();
		
		int level=tree.maxHeight(root);
		System.out.println("Tree level = "+ level);
	}
	
}
